import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.util.*;

/**
 * @Author: wangliuyang
 * @Date: 2021/9/6 18:56
 * @Description:46. 全排列
 */
public class Solution_46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();;
        permuted(nums,0,list);
        return list;
    }

    public void permuted(int[] nums, int index, List<List<Integer>> list) {
        if (index == nums.length){
            ArrayList<Integer> arrayList = new ArrayList<>();
            for (int num : nums) {
                arrayList.add(num);
            }
            list.add(arrayList);
            return;
        }
        for (int i = index; i < nums.length; i++) {
            swap(nums,index,i);
            permuted(nums,index + 1,list);
            swap(nums,index,i);
        }
    }

    private void swap(int[] nums, int index, int i) {
        if (index == i){
            return;
        }
        nums[index] = nums[i] ^ nums[index];
        nums[i] = nums[i] ^ nums[index];
        nums[index] = nums[i] ^ nums[index];
    }


}
